'''
https://leetcode.cn/problems/the-maze-iii/description
'''
import heapq
from typing import List


class Solution:
    def findShortestWay(self, maze: List[List[int]], start: List[int], destination: List[int]) -> str:
        destination = tuple(destination)
        m, n = len(maze), len(maze[0])
        visited = [[False] * n for _ in range(m)]
        distances = [[float('inf')] * n for _ in range(m)]
        paths = [['z'] * n for _ in range(m)]
        pq = [(0, '', start[0], start[1])]  # cost,path, (i,j)
        while pq:
            cost, path, i, j = heapq.heappop(pq)
            if (i, j) == destination:
                return path
            if visited[i][j]: continue
            visited[i][j] = True
            for dx, dy, info in [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]:
                x, y = i + dx, j + dy
                cur_cost = cost
                cur_path = path + info
                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
                    if (x, y) == destination:
                        x, y = x + dx, y + dy
                        break
                    x, y = x + dx, y + dy
                    cur_cost += 1
                x, y = x - dx, y - dy
                if cur_cost < distances[x][y] or (cur_cost == distances[x][y] and cur_path < paths[x][y]):
                    distances[x][y] = cur_cost
                    paths[x][y] = cur_path
                    heapq.heappush(pq, (cur_cost, cur_path, x, y))
        return 'impossible'


# maze = [[0,0,0,0,a,0,0],
#         [0,0,1,0,0,1,0],
#         [b,0,0,0,1,0,0],
#         [0,0,0,0,0,0,1]]
# maze = [[0, 0, 0, 0, 0, 0, 0],
#         [0, 0, 1, 0, 0, 1, 0],
#         [0, 0, 0, 0, 1, 0, 0],
#         [0, 0, 0, 0, 0, 0, 1]]
# ball = [0, 4]
# hole = [2, 0]
# print('ul' < 'lul')
# print('lul' < 'ul')
# maze = [[0, b, 0, 0, 0],
#         [1, 1, 0, 0, 1],
#         [0, 0, 0, 0, 0],
#         [0, 1, 0, 0, 1],
#         [0, 1, 0, a, 0]]
maze = [[0, 0, 0, 0, 0],
        [1, 1, 0, 0, 1],
        [0, 0, 0, 0, 0],
        [0, 1, 0, 0, 1],
        [0, 1, 0, 0, 0]]
ball = [4, 3]
hole = [0, 1]
print(Solution().findShortestWay(maze, ball, hole))
